package com.lbt.javaSE.tanxin;

import java.util.Arrays;
import java.util.Scanner;

public class CoinChange {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        Integer coins[]=new Integer[]{1,25,20,5};   //TODO 贪心不能实现最优解的反例
        Arrays.sort(coins,(Integer f1,Integer f2)->f2-f1);  //自定义比较器 从大到小排列
        int money=0,count=0;        //money=41
        int i=0;
        money=sc.nextInt();
        System.out.println("用这几个面值的硬币兑换");
        while(i<coins.length){
            if(money<coins[i]){ //剩于钱数小于面值
                i++;
                continue;
            }
            System.out.print(coins[i]+"\t");
            money-=coins[i];
            count++;
        }
        System.out.println("\n需要"+count+"枚硬币!");
    }
}
